<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Thread coordination using Boost.Atomic</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../atomic.html" title="Chapter 6. Boost.Atomic">
<link rel="prev" href="../atomic.html" title="Chapter 6. Boost.Atomic">
<link rel="next" href="interface.html" title="Programming interfaces">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../atomic.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../atomic.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="interface.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="atomic.thread_coordination"></a><a class="link" href="thread_coordination.html" title="Thread coordination using Boost.Atomic">Thread coordination using Boost.Atomic</a>
</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="thread_coordination.html#atomic.thread_coordination.mutex">Enforcing <span class="emphasis"><em>happens-before</em></span>
      through mutual exclusion</a></span></dt>
<dt><span class="section"><a href="thread_coordination.html#atomic.thread_coordination.release_acquire"><span class="emphasis"><em>happens-before</em></span>
      through <code class="literal">release</code> and <code class="literal">acquire</code></a></span></dt>
<dt><span class="section"><a href="thread_coordination.html#atomic.thread_coordination.fences">Fences</a></span></dt>
<dt><span class="section"><a href="thread_coordination.html#atomic.thread_coordination.release_consume"><span class="emphasis"><em>happens-before</em></span>
      through <code class="literal">release</code> and <code class="literal">consume</code></a></span></dt>
<dt><span class="section"><a href="thread_coordination.html#atomic.thread_coordination.seq_cst">Sequential consistency</a></span></dt>
</dl></div>
<p>
      The most common use of <span class="bold"><strong>Boost.Atomic</strong></span> is to
      realize custom thread synchronization protocols: The goal is to coordinate
      accesses of threads to shared variables in order to avoid "conflicts".
      The programmer must be aware of the fact that compilers, CPUs and the cache
      hierarchies may generally reorder memory references at will. As a consequence
      a program such as:
    </p>
<pre class="programlisting"><span class="keyword">int</span> <span class="identifier">x</span> <span class="special">=</span> <span class="number">0</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">y</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span>

<span class="identifier">thread1</span><span class="special">:</span>
  <span class="identifier">x</span> <span class="special">=</span> <span class="number">1</span><span class="special">;</span>
  <span class="identifier">y</span> <span class="special">=</span> <span class="number">1</span><span class="special">;</span>

<span class="identifier">thread2</span><span class="special">:</span>
  <span class="keyword">if</span> <span class="special">(</span><span class="identifier">y</span> <span class="special">==</span> <span class="number">1</span><span class="special">)</span> <span class="special">{</span>
    <span class="identifier">assert</span><span class="special">(</span><span class="identifier">x</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span>
  <span class="special">}</span>
</pre>
<p>
      might indeed fail as there is no guarantee that the read of <code class="computeroutput"><span class="identifier">x</span></code>
      by thread2 "sees" the write by thread1.
    </p>
<p>
      <span class="bold"><strong>Boost.Atomic</strong></span> uses a synchronisation concept
      based on the <span class="emphasis"><em>happens-before</em></span> relation to describe the guarantees
      under which situations such as the above one cannot occur.
    </p>
<p>
      The remainder of this section will discuss <span class="emphasis"><em>happens-before</em></span>
      in a "hands-on" way instead of giving a fully formalized definition.
      The reader is encouraged to additionally have a look at the discussion of the
      correctness of a few of the <a class="link" href="usage_examples.html" title="Usage examples">examples</a>
      afterwards.
    </p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="atomic.thread_coordination.mutex"></a><a class="link" href="thread_coordination.html#atomic.thread_coordination.mutex" title="Enforcing happens-before through mutual exclusion">Enforcing <span class="emphasis"><em>happens-before</em></span>
      through mutual exclusion</a>
</h3></div></div></div>
<p>
        As an introductory example to understand how arguing using <span class="emphasis"><em>happens-before</em></span>
        works, consider two threads synchronizing using a common mutex:
      </p>
<pre class="programlisting"><span class="identifier">mutex</span> <span class="identifier">m</span><span class="special">;</span>

<span class="identifier">thread1</span><span class="special">:</span>
  <span class="identifier">m</span><span class="special">.</span><span class="identifier">lock</span><span class="special">();</span>
  <span class="special">...</span> <span class="comment">/* A */</span>
  <span class="identifier">m</span><span class="special">.</span><span class="identifier">unlock</span><span class="special">();</span>

<span class="identifier">thread2</span><span class="special">:</span>
  <span class="identifier">m</span><span class="special">.</span><span class="identifier">lock</span><span class="special">();</span>
  <span class="special">...</span> <span class="comment">/* B */</span>
  <span class="identifier">m</span><span class="special">.</span><span class="identifier">unlock</span><span class="special">();</span>
</pre>
<p>
        The "lockset-based intuition" would be to argue that A and B cannot
        be executed concurrently as the code paths require a common lock to be held.
      </p>
<p>
        One can however also arrive at the same conclusion using <span class="emphasis"><em>happens-before</em></span>:
        Either thread1 or thread2 will succeed first at <code class="literal">m.lock()</code>.
        If this is be thread1, then as a consequence, thread2 cannot succeed at
        <code class="literal">m.lock()</code> before thread1 has executed <code class="literal">m.unlock()</code>,
        consequently A <span class="emphasis"><em>happens-before</em></span> B in this case. By symmetry,
        if thread2 succeeds at <code class="literal">m.lock()</code> first, we can conclude
        B <span class="emphasis"><em>happens-before</em></span> A.
      </p>
<p>
        Since this already exhausts all options, we can conclude that either A <span class="emphasis"><em>happens-before</em></span>
        B or B <span class="emphasis"><em>happens-before</em></span> A must always hold. Obviously
        cannot state <span class="emphasis"><em>which</em></span> of the two relationships holds, but
        either one is sufficient to conclude that A and B cannot conflict.
      </p>
<p>
        Compare the <a class="link" href="usage_examples.html#boost_atomic.usage_examples.example_spinlock" title="Spinlock">spinlock</a>
        implementation to see how the mutual exclusion concept can be mapped to
        <span class="bold"><strong>Boost.Atomic</strong></span>.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="atomic.thread_coordination.release_acquire"></a><a class="link" href="thread_coordination.html#atomic.thread_coordination.release_acquire" title="happens-before through release and acquire"><span class="emphasis"><em>happens-before</em></span>
      through <code class="literal">release</code> and <code class="literal">acquire</code></a>
</h3></div></div></div>
<p>
        The most basic pattern for coordinating threads via <span class="bold"><strong>Boost.Atomic</strong></span>
        uses <code class="literal">release</code> and <code class="literal">acquire</code> on an atomic
        variable for coordination: If ...
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            ... thread1 performs an operation A,
          </li>
<li class="listitem">
            ... thread1 subsequently writes (or atomically modifies) an atomic variable
            with <code class="literal">release</code> semantic,
          </li>
<li class="listitem">
            ... thread2 reads (or atomically reads-and-modifies) the value this value
            from the same atomic variable with <code class="literal">acquire</code> semantic
            and
          </li>
<li class="listitem">
            ... thread2 subsequently performs an operation B,
          </li>
</ul></div>
<p>
        ... then A <span class="emphasis"><em>happens-before</em></span> B.
      </p>
<p>
        Consider the following example
      </p>
<pre class="programlisting"><span class="identifier">atomic</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">a</span><span class="special">(</span><span class="number">0</span><span class="special">);</span>

<span class="identifier">thread1</span><span class="special">:</span>
  <span class="special">...</span> <span class="comment">/* A */</span>
  <span class="identifier">a</span><span class="special">.</span><span class="identifier">fetch_add</span><span class="special">(</span><span class="number">1</span><span class="special">,</span> <span class="identifier">memory_order_release</span><span class="special">);</span>

<span class="identifier">thread2</span><span class="special">:</span>
  <span class="keyword">int</span> <span class="identifier">tmp</span> <span class="special">=</span> <span class="identifier">a</span><span class="special">.</span><span class="identifier">load</span><span class="special">(</span><span class="identifier">memory_order_acquire</span><span class="special">);</span>
  <span class="keyword">if</span> <span class="special">(</span><span class="identifier">tmp</span> <span class="special">==</span> <span class="number">1</span><span class="special">)</span> <span class="special">{</span>
    <span class="special">...</span> <span class="comment">/* B */</span>
  <span class="special">}</span> <span class="keyword">else</span> <span class="special">{</span>
    <span class="special">...</span> <span class="comment">/* C */</span>
  <span class="special">}</span>
</pre>
<p>
        In this example, two avenues for execution are possible:
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            The <code class="literal">store</code> operation by thread1 precedes the <code class="literal">load</code>
            by thread2: In this case thread2 will execute B and "A <span class="emphasis"><em>happens-before</em></span>
            B" holds as all of the criteria above are satisfied.
          </li>
<li class="listitem">
            The <code class="literal">load</code> operation by thread2 precedes the <code class="literal">store</code>
            by thread1: In this case, thread2 will execute C, but "A <span class="emphasis"><em>happens-before</em></span>
            C" does <span class="emphasis"><em>not</em></span> hold: thread2 does not read the
            value written by thread1 through <code class="literal">a</code>.
          </li>
</ul></div>
<p>
        Therefore, A and B cannot conflict, but A and C <span class="emphasis"><em>can</em></span>
        conflict.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="atomic.thread_coordination.fences"></a><a class="link" href="thread_coordination.html#atomic.thread_coordination.fences" title="Fences">Fences</a>
</h3></div></div></div>
<p>
        Ordering constraints are generally specified together with an access to an
        atomic variable. It is however also possible to issue "fence" operations
        in isolation, in this case the fence operates in conjunction with preceding
        (for <code class="computeroutput"><span class="identifier">acquire</span></code>, <code class="computeroutput"><span class="identifier">consume</span></code> or <code class="computeroutput"><span class="identifier">seq_cst</span></code>
        operations) or succeeding (for <code class="computeroutput"><span class="identifier">release</span></code>
        or <code class="computeroutput"><span class="identifier">seq_cst</span></code>) atomic operations.
      </p>
<p>
        The example from the previous section could also be written in the following
        way:
      </p>
<pre class="programlisting"><span class="identifier">atomic</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">a</span><span class="special">(</span><span class="number">0</span><span class="special">);</span>

<span class="identifier">thread1</span><span class="special">:</span>
  <span class="special">...</span> <span class="comment">/* A */</span>
  <span class="identifier">atomic_thread_fence</span><span class="special">(</span><span class="identifier">memory_order_release</span><span class="special">);</span>
  <span class="identifier">a</span><span class="special">.</span><span class="identifier">fetch_add</span><span class="special">(</span><span class="number">1</span><span class="special">,</span> <span class="identifier">memory_order_relaxed</span><span class="special">);</span>

<span class="identifier">thread2</span><span class="special">:</span>
  <span class="keyword">int</span> <span class="identifier">tmp</span> <span class="special">=</span> <span class="identifier">a</span><span class="special">.</span><span class="identifier">load</span><span class="special">(</span><span class="identifier">memory_order_relaxed</span><span class="special">);</span>
  <span class="keyword">if</span> <span class="special">(</span><span class="identifier">tmp</span> <span class="special">==</span> <span class="number">1</span><span class="special">)</span> <span class="special">{</span>
    <span class="identifier">atomic_thread_fence</span><span class="special">(</span><span class="identifier">memory_order_acquire</span><span class="special">);</span>
    <span class="special">...</span> <span class="comment">/* B */</span>
  <span class="special">}</span> <span class="keyword">else</span> <span class="special">{</span>
    <span class="special">...</span> <span class="comment">/* C */</span>
  <span class="special">}</span>
</pre>
<p>
        This provides the same ordering guarantees as previously, but elides a (possibly
        expensive) memory ordering operation in the case C is executed.
      </p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p>
          Atomic fences are only indended to constraint ordering of regular and atomic
          loads and stores for the purpose of thread synchronization. <code class="computeroutput"><span class="identifier">atomic_thread_fence</span></code> is not intended to
          be used to order some architecture-specific memory accesses, such as non-temporal
          loads and stores on x86 or write combining memory accesses. Use specialized
          instructions for these purposes.
        </p></td></tr>
</table></div>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="atomic.thread_coordination.release_consume"></a><a class="link" href="thread_coordination.html#atomic.thread_coordination.release_consume" title="happens-before through release and consume"><span class="emphasis"><em>happens-before</em></span>
      through <code class="literal">release</code> and <code class="literal">consume</code></a>
</h3></div></div></div>
<p>
        The second pattern for coordinating threads via <span class="bold"><strong>Boost.Atomic</strong></span>
        uses <code class="literal">release</code> and <code class="literal">consume</code> on an atomic
        variable for coordination: If ...
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            ... thread1 performs an operation A,
          </li>
<li class="listitem">
            ... thread1 subsequently writes (or atomically modifies) an atomic variable
            with <code class="literal">release</code> semantic,
          </li>
<li class="listitem">
            ... thread2 reads (or atomically reads-and-modifies) the value this value
            from the same atomic variable with <code class="literal">consume</code> semantic
            and
          </li>
<li class="listitem">
            ... thread2 subsequently performs an operation B that is <span class="emphasis"><em>computationally
            dependent on the value of the atomic variable</em></span>,
          </li>
</ul></div>
<p>
        ... then A <span class="emphasis"><em>happens-before</em></span> B.
      </p>
<p>
        Consider the following example
      </p>
<pre class="programlisting"><span class="identifier">atomic</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">a</span><span class="special">(</span><span class="number">0</span><span class="special">);</span>
<span class="identifier">complex_data_structure</span> <span class="identifier">data</span><span class="special">[</span><span class="number">2</span><span class="special">];</span>

<span class="identifier">thread1</span><span class="special">:</span>
  <span class="identifier">data</span><span class="special">[</span><span class="number">1</span><span class="special">]</span> <span class="special">=</span> <span class="special">...;</span> <span class="comment">/* A */</span>
  <span class="identifier">a</span><span class="special">.</span><span class="identifier">store</span><span class="special">(</span><span class="number">1</span><span class="special">,</span> <span class="identifier">memory_order_release</span><span class="special">);</span>

<span class="identifier">thread2</span><span class="special">:</span>
  <span class="keyword">int</span> <span class="identifier">index</span> <span class="special">=</span> <span class="identifier">a</span><span class="special">.</span><span class="identifier">load</span><span class="special">(</span><span class="identifier">memory_order_consume</span><span class="special">);</span>
  <span class="identifier">complex_data_structure</span> <span class="identifier">tmp</span> <span class="special">=</span> <span class="identifier">data</span><span class="special">[</span><span class="identifier">index</span><span class="special">];</span> <span class="comment">/* B */</span>
</pre>
<p>
        In this example, two avenues for execution are possible:
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            The <code class="literal">store</code> operation by thread1 precedes the <code class="literal">load</code>
            by thread2: In this case thread2 will read <code class="literal">data[1]</code>
            and "A <span class="emphasis"><em>happens-before</em></span> B" holds as all
            of the criteria above are satisfied.
          </li>
<li class="listitem">
            The <code class="literal">load</code> operation by thread2 precedes the <code class="literal">store</code>
            by thread1: In this case thread2 will read <code class="literal">data[0]</code>
            and "A <span class="emphasis"><em>happens-before</em></span> B" does <span class="emphasis"><em>not</em></span>
            hold: thread2 does not read the value written by thread1 through <code class="literal">a</code>.
          </li>
</ul></div>
<p>
        Here, the <span class="emphasis"><em>happens-before</em></span> relationship helps ensure that
        any accesses (presumable writes) to <code class="literal">data[1]</code> by thread1
        happen before before the accesses (presumably reads) to <code class="literal">data[1]</code>
        by thread2: Lacking this relationship, thread2 might see stale/inconsistent
        data.
      </p>
<p>
        Note that in this example, the fact that operation B is computationally dependent
        on the atomic variable, therefore the following program would be erroneous:
      </p>
<pre class="programlisting"><span class="identifier">atomic</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">a</span><span class="special">(</span><span class="number">0</span><span class="special">);</span>
<span class="identifier">complex_data_structure</span> <span class="identifier">data</span><span class="special">[</span><span class="number">2</span><span class="special">];</span>

<span class="identifier">thread1</span><span class="special">:</span>
  <span class="identifier">data</span><span class="special">[</span><span class="number">1</span><span class="special">]</span> <span class="special">=</span> <span class="special">...;</span> <span class="comment">/* A */</span>
  <span class="identifier">a</span><span class="special">.</span><span class="identifier">store</span><span class="special">(</span><span class="number">1</span><span class="special">,</span> <span class="identifier">memory_order_release</span><span class="special">);</span>

<span class="identifier">thread2</span><span class="special">:</span>
  <span class="keyword">int</span> <span class="identifier">index</span> <span class="special">=</span> <span class="identifier">a</span><span class="special">.</span><span class="identifier">load</span><span class="special">(</span><span class="identifier">memory_order_consume</span><span class="special">);</span>
  <span class="identifier">complex_data_structure</span> <span class="identifier">tmp</span><span class="special">;</span>
  <span class="keyword">if</span> <span class="special">(</span><span class="identifier">index</span> <span class="special">==</span> <span class="number">0</span><span class="special">)</span>
    <span class="identifier">tmp</span> <span class="special">=</span> <span class="identifier">data</span><span class="special">[</span><span class="number">0</span><span class="special">];</span>
  <span class="keyword">else</span>
    <span class="identifier">tmp</span> <span class="special">=</span> <span class="identifier">data</span><span class="special">[</span><span class="number">1</span><span class="special">];</span>
</pre>
<p>
        <code class="literal">consume</code> is most commonly (and most safely! see <a class="link" href="limitations.html" title="Limitations">limitations</a>)
        used with pointers, compare for example the <a class="link" href="usage_examples.html#boost_atomic.usage_examples.singleton" title="Singleton with double-checked locking pattern">singleton
        with double-checked locking</a>.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="atomic.thread_coordination.seq_cst"></a><a class="link" href="thread_coordination.html#atomic.thread_coordination.seq_cst" title="Sequential consistency">Sequential consistency</a>
</h3></div></div></div>
<p>
        The third pattern for coordinating threads via <span class="bold"><strong>Boost.Atomic</strong></span>
        uses <code class="literal">seq_cst</code> for coordination: If ...
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            ... thread1 performs an operation A,
          </li>
<li class="listitem">
            ... thread1 subsequently performs any operation with <code class="literal">seq_cst</code>,
          </li>
<li class="listitem">
            ... thread1 subsequently performs an operation B,
          </li>
<li class="listitem">
            ... thread2 performs an operation C,
          </li>
<li class="listitem">
            ... thread2 subsequently performs any operation with <code class="literal">seq_cst</code>,
          </li>
<li class="listitem">
            ... thread2 subsequently performs an operation D,
          </li>
</ul></div>
<p>
        then either "A <span class="emphasis"><em>happens-before</em></span> D" or "C
        <span class="emphasis"><em>happens-before</em></span> B" holds.
      </p>
<p>
        In this case it does not matter whether thread1 and thread2 operate on the
        same or different atomic variables, or use a "stand-alone" <code class="literal">atomic_thread_fence</code>
        operation.
      </p>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2011 Helge Bahmann<br>Copyright © 2012 Tim Blechmann<br>Copyright © 2013, 2017, 2018, 2020, 2021 Andrey Semashev<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../atomic.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../atomic.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="interface.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
